public class Sort {
    // 1.插入排序


    /**
     *  时间复杂度：O(N^2)
     *   最好情况的时间复杂度是O(N)
     *     当数据趋于有序的时候，排序的速度非常快。 一般的场景就是数据基本有序 建议使用直接插入排序
     *  空间复杂度：O(1)
     *  稳定性：稳定
     *  如果一个排序是稳定的 就可以实现为不稳定的
     *  如果一个排序本身就是不稳定的 那么你就无法实现一个稳定的排序
     *
     * @param array
     */

    // 1.1直接插入排序
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for ( ; j >=0 ; j--) {
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else {
                 //   array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

   /**
     *  时间复杂度 ： O(N^1.3) --- O(N^1.5)  (把O(N^1.3)记住就行)
     *  空间复杂度 ： O(1)
     *  稳定性 ：不稳定的排序
     * @param array
     */

    // 1.2希尔排序（缩小增量排序）
    // 也是插入排序的一种优化
    // 在这里面 每一次分组按照 （ n / 2 ）+ 1 来计算分组
    // 因为希尔排序有着尚未解决的分组问题
    public static void shellSort(int[] array){
        int gap = array.length;
        // 下面开始进行分组

        // 1.当gap > 1 时
        while(gap > 1){
            // 并且每一个增量里面又是一个插入排序
            shell(array,gap);
            // 开始缩小增量
            gap /= 2;  // 把 gap的缩小增量换入在这一行那就需要 在循环结束后在进行 2步骤 shell一次
        }
        // 2.当 gap = 1 时 整体进行插入排序
        shell(array,1);
    }
        // 插入排序
    public static void shell(int[] array, int gap){
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for ( ; j >=0 ; j-=gap) {
                if(array[j] > tmp){
                    array[j+gap] = array[j];
                }else {
                    //   array[j+1] = tmp;
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }



    // 2.选择排序

    /**
     * 时间复杂度 O(N^2)
     * 空间复杂度 O(1) 因为还是没有申请额外的空间
     * 稳定性 不稳定
     * @param array
     */
    //2.1 直接选择排序
    // 原理：在后面找到一个最小的放到前面来
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            int j = i+1;
            for (; j < array.length; j++) {
                if(array[minIndex] > array[j]){
                    minIndex = j;
                }
            }
           /* int tmp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = tmp;*/
            swap(array,i,minIndex);
        }
    }
    private  static void swap(int[] array, int i , int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }


    /**
     *  时间复杂度O(N^2)
     * @param array
     */
    // 选择排序的第二种方式

    public static void selectSort2(int[] array){
        int left = 0;
        int right = array.length-1;
        while(left < right){
            int minIndex = left; // 假定这是最小值的下标
            int maxIndex = left; // 假定这是最大值的下标

            for (int i = left+1; i <= right; i++) {
                if(array[i] < array[minIndex]){
                    minIndex = i;
                }
                if(array[i] > array[maxIndex]){
                    maxIndex = i;
                }
            }

            swap(array,minIndex , left); // 这里有可能把最大值换到minIndex的位置
            //言外之意 一开始的最大值正好在最开始left的位置

            if (maxIndex == left){
                maxIndex = minIndex;
            }

            swap(array , maxIndex ,right);

            left++;
            right--;
        }
    }

    /**
     * 堆排序：
     * 时间复杂度时O(N*logN)
     * 空间复杂度是  O(1)
     * 稳定性 不稳定的
     */
    // 2.2堆排序
    public static void heapSort(int[] array){
        // 创建大根堆
        createBigHeap(array);
        // 然后开始排序
        int end = array.length - 1;
        while(end > 0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }
    // 需要先创建一个大根堆
    private static void createBigHeap(int[] array){
        for (int parent = (array.length-1-1) / 2 ; parent >= 0 ; parent--){
            shiftDown(array,parent,array.length);
        }
    }

    private  static  void shiftDown(int[] array , int parent , int len){
        int child = 2*parent+1;
        while(child < len){
            if(child+1 < len && array[child] < array[child+1]){
                child++;
            }
            if(array[child] > array[parent]){
                swap(array,child,parent);
                parent =child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

    // 3.交换排序

    /**
     * 冒泡排序
     * 时间复杂度 (不考虑优化) O(N)
     * 空间复杂度 O(1)
     * 稳定性 稳定的
     * @param array
     */
    //3.1 冒泡排序
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            boolean flag = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]){
                    swap(array,j,j+1);
                    flag =true;
                }
            }
            if(flag == false){
                return;
            }
        }
    }

    /**
     * 快速排序
     *
     * 时间复杂度: O(N*logN) 跟二叉树一样
     *          最好情况：O(N*logN)
     *          最坏情况：N^2 有序或者逆序的情况 这种情况是需要进行优化
     * 空间复杂度: O()
     *          最好情况：（满二叉树） O(logN)
     *          最坏情况： O(N)
     * 稳定性: 不稳定的
     *
     * @param array
     */
    // 3.2 快速排序


    public static  void quickSort(int[] array){
        quick(array,0,array.length-1);
        // 首先要找到一个基准
        // 并且以这个基准开始划分
        // 因为划分是一个公共的 所以把划分单独写成一个函数
    }
    public static void quick(int[] array, int start , int end){

        // 判断基准是否结束
        if(start >= end){  // 这里面的 >= 是因为 end传入的值是pivot-1 会 小于 start
            return;
        }

        // 写完三数取中后还可以继续优化一边
        // 我们发现二叉树的后两层基本上包含了二叉树的全部
        // 当我们再排序的时候 后两层可以按照直接插入的方式来排序 这样就不用再递归申请空间了
        // 适合end 和 start之间的数据剩余很少的情况
        if (end - start+1 <= 14/*这里面写自己给定的一个值 以14为例*/){
            // 插入排序
            insertSort2(array,start,end); //(主要是减少递归的次数)
            return;
        }

       // System.out.println("start:"+start+" end:"+end);

        // 在这个函数里面开始排序

        // 首先要定义一个基准 pivot
     //   int pivot = partition(array,start,end); // 划分
       // int pivot = partition2(array,start,end); // 划分

       // 接下来用三数取中法
        int index = midThree(array,start,end);
        // 将找到的这个中间值和起始位置开始交换
        swap(array,index, start);
        // 然后继续以我们写的方法作为它的基准
        int pivot = partition2(array,start,end); // 划分

        // 接下来递归开始找基准
        quick(array,start,pivot-1);  // 基准左边的区域
        quick(array,pivot+1,end); // 基准右边的区域



    }
    // 划分
    // 方法一 ： 挖坑法
    private static int partition(int[] array, int left , int right){
        // 定义一个 tmp 临时变量
        int tmp = array[left]; // 初始值是最左边的值
        while(left < right){
            while(array[right] >= tmp && left < right){ // >=  这里面的等号是必须加的
                // 开始判断tmp 右边的值是否大于tmp
                // 因为右边是找要比tmp小的值
                // 如果比 tmp 大的话right就要往前移
                right--;
                // left < right 是为了防止最后越界
            }
            // 这循环如果走完了 ， 呢就说明找到了比tmp小的值
            // 所以把 right 的值放到left的地方
            array[left] = array[right];
            // 交换完之后开始走left
            // 走left是找到比tmp大的值
            while(array[left] <= tmp && left < right){
                // 小于的话就继续找
                left++;
            }
            // 到这一行的话就说明找到了
            array[right] = array[left]; // 把left 的值放到right当中
            // 之后重复以上操作
        }
        //走完之后 left 和 right 相遇了
        // 就把 tmp 的 值存放到left 的位置上
        array[left] = tmp;
        return left; // 返回当前基准的下标
    }

    // 第二种方法
    //  Hoare版
    // 做法和挖坑法大相径庭 就是
    // right 先找 找到比 刚开始的基准 小的就停下来
    // 然后left就开始找 找到比 基准大的也停下来
    // 然后开始交换right 和 left 的值开始交换
    // 当最后两者相遇的时候在把这个基准存放到相遇的位置

    private static int partition2(int[] array, int left , int right){
        int tmp = array[left];
        int i = left; // 记录开始时的left位置
        while(left < right){
            while(array[right] >= tmp && left < right){
                right--;
            }
            while(array[left] <= tmp && left < right){
                left++;
            }
            swap(array,right,left);
        }
        // 相遇之后 再交换一次 left 和 初始时start的位置的值
        swap(array,left,i);
        return left;
    }


    // 第三中方法
    // 前后指针法（了解即可）
    private static int partition3(int[] array, int left , int right){
        // 定义两个指针
        int prev = left ; // 记录的永远是一个比当前基准值小的最后一个数
        int cur = left+1;
        while (cur <= right) {
            if(array[cur] < array[left] && array[++prev] != array[cur]) { // 并且 prev的后一个不等于cur的时候
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }
    // 快排 会有一种局限 ，那就是一旦当数据过多的时候就有可能会造成栈溢出的现象

    // 那么有一下两种方法
    // 1.随机选取基准法
    // 但是也有缺陷的（需要看“人品”）

    //
    // 2.三数取中法 （这个更靠谱一点）
    // 这三个数 分别是 第一个 中间的 最后的
    // 从这三个数中选出一个不是最大的也不是最小的数
    // 这个地方有可能会变成二分查找（因为这样不会再出现 刚刚最坏的情况了）
    private static int midThree(int[] array,int left,int right){
        int mid = (left+right) / 2;
        // 那么如何找到最大值和最小值
        if(array[left] < array[right]){
            if (array[mid] < array[left]){
                return left;
            } else if (array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid] > array[left]){
                return  left;
            }else if(array[mid] < array[right]){
                return right;
            }else {
                return mid;
            }
        }
     }


    /**
     * 非递归实现快排
     * @param array
     */
     public static void quickSORT(int[] array){
         // 用到栈
         Deque<Integer> stack = new LinkedList<>();
         // 还是先找到基准
         int left = 0;
         int right = array.length-1;
        int pivot = partition(array,left,right);
        // 接下来用非递归的方式去写
         if(pivot > left+1){
             // 这个说明基准的左边（包括基准本身）不是剩两个元素了 //pivot = left+1 这个说明基准的左边只剩下一个元素了
             // 如果只剩下两个元素就不用再排序了
             stack.push(left);
             stack.push(pivot-1); // 这两个顺序不能交换
         }
         if(pivot < right-1){
             // 这个说明基准的右边不是剩两个元素了  // pivot = right-1 这个说明基准的右边只剩下一个元素了
             // 如果只剩下两个元素就不用再排序了
             stack.push(pivot+1);
             stack.push(right);// 这两个顺序不能交换
         }
        // 然后循环栈不是空的情况
         while (!stack.isEmpty()){
             // 先弹出一个给右边的值
             right = stack.pop();
             // 再弹出一个给左边的值
             left = stack.pop(); // 这个顺序不能改变
             // 重复上述操作
             pivot = partition(array,left,right);
             // 接下来用非递归的方式去写
             if(pivot > left+1){
                 // 这个说明基准的左边（包括基准本身）就剩两个元素了
                 stack.push(left);
                 stack.push(pivot-1); // 这两个顺序不能交换
             }
             if(pivot < right-1){
                 // 这个说明基准的右边只剩两个元素了
                 stack.push(pivot+1);
                 stack.push(right);// 这两个顺序不能交换
             }
         }
     }


    /**
     *  时间复杂度 NlogN
     *  空间复杂度 O(N)
     *  稳定性：稳定的排序
     * @param array
     */
     // **** 归并排序****

    // 步骤
    public static void mergeSort(int[] array){
        mergeSortFunc(array,0,array.length-1);
    }
    // 归并函数
    private  static void mergeSortFunc(int[] array,int left,int right){
         if(left>=right){
             return;
        }
         // 确定中间值
         int mid = (left+right) / 2;
         // 接下来开始分解
         mergeSortFunc(array,left,mid);
         mergeSortFunc(array,mid+1,right);
         // 到这里分解完了

        // 现在开始合并
        merge(array,left,right,mid);
    }

    // 合并
    private static void merge(int[] array,int start,int end,int mid){
         int s1 = start;
       //  int e1 = mid;
         int s2 = mid+1;
         int e2 = end;

         int[] tmp = new int[end - start + 1];
         int k = 0; //表示tmp数组的下标
         //接下来开始比较
        // 每次都拿是s1和s2去比较
        while(s1 <= mid && s2 <= end){
            //谁小把谁放入新的数组
            // 需要创建新的数组
            if(array[s1] <= array[s2]){
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
                /*k++;
                s2++;*/
            }
        }
        // 走完之后 会剩余的值没有存到新的数组中
        // 所以我们要判断是谁没有被存进去
        while(s1 <= mid){
            tmp[k++] = array[s1++];
        }
        while(s2 <= end){
            tmp[k++] = array[s2++];
        }

        // tmp排完之后不是原数组的值
        // 所以需要把tmp里面的值再存放到array当中
        for (int i = 0; i < tmp.length; i++) {
           // array[i] = tmp[i]; // 但是只写这一行是有问题的
            //因为再拷贝右边的时候array的下标是从中间开始的
            // 而 tmp 还是从零开始 这是不匹配的
            // 解决方法
            array[i+start] = tmp[i];
        }
    }

    // 归并排序的非递归实现
    public static void mergeSort2(int[] array){
        int gap = 1; // gap表示有多少组 初始值为1 （组）
        while(gap < array.length){ // 当每一个组数等于数组长度的时候就结束排序
            for (int i = 0; i < array.length; i = i+gap*2) {
                //i+gap*2 当前gap组的时候，去排序的下一个组段
                int left = i;
                int mid = left+gap -1;
                if(mid >= array.length){
                    mid = array.length-1;
                }
                int right = mid+gap;
                // 但是这里的mid和right有可能会越界
                //所以要进行判断
                if(right>=array.length){
                    right = array.length - 1;
                }
                // 接下来开始合并
                merge(array,left,right,mid);
            }
            //如 当前为 2 组有序 下次变成 4 组有序
            gap = gap*2;

        }
    }
    
    /**
     *    时间复杂度：O(MAX(N,范围))
     *    空间复杂度：O(范围)
     *    稳定性：稳定
     */
    // 计数排序

    // 第一步： 遍历数组找到最大值
    public static void countSort(int[] array){
         // 1.遍历数组找到最大值和最小值
        int max = array[0];
        int min = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] < min){
                min = array[i];
            }
            if(array[i] > max){
                max = array[i];
            }
        }
        
        // 根据范围定义计数数组的长度
        int len = max - min + 1;
        int[] count = new int[len];
        
        //3.遍历数组， 在计数数组当中记录每个数字出现的次数
        for (int i = 0; i < array.length; i++) {
            count[array[i]-min]++;
        }

        // 4. 遍历计数数组
        int index = 0;//array 数组的新的下标
        for (int i = 0; i < count.length; i++) {
            while(count[i]>0){
                // 这里要加上最小值才能反应真实的数据
                array[index] = i+min;
                index++;
                count[i]--;
            }
        }
        
    }
}
